package arithmetic;

import java.util.Arrays;
import java.util.Random;
import java.util.stream.Stream;

import cn.hutool.core.date.StopWatch;

/**
 * 求组小和
 * 数组小和的定义如下：
 * <p>
 * 例如，数组s=[ 1,3,5,2,4,6],在s[0]的左边小于或等于s[0]的数的和为0,在s[l]的左边 小于或等于s[l]的数的和为1,
 * <p>
 * 在s[2]的左边小于或等于s[2]的数的和为1+3=4,
 * <p>
 * 在s[3]的 左边小于或等于s[3]的数的和为1,
 * <p>
 * 在s[4]的左边小于或等于s[4]的数的和为1+3+2=6,
 * <p>
 * 在 s[5]的左边小于或等于s[5]的数的和为1+3+5+2+4=15,所以s的小和为0+1+4+1+6+15=27。
 * <p>
 * 给定一个数组s,实现函数返回s的小和。
 * -----------------------------------
 * ©著作权归作者所有：来自51CTO博客作者认知与技术成长的原创作品，请联系作者获取转载授权，否则将追究法律责任
 * 快手高频面试题之计算数组小和（相关话题：归并排序，双指针）
 * https://blog.51cto.com/u_13270164/3035922
 *
 * @author jiangfeng on 2022/5/30
 */
public class GroupSmallSum {
    public static int count1 = 0;
    public static int count2 = 0;
    public static int count3 = 0;

    public static void main(String[] args) {
        //int[] a = {1,3,5,2,4,6,7,5};
        //int[] a = {1,3,5,7,9,11,13,14};

        Random random = new Random();

        /**
         * -95754247
         * smallSum3
         * -95754247
         * StopWatch '': running time = 2555184706 ns
         * ---------------------------------------------
         * ns         %     Task name
         * ---------------------------------------------
         * 2537280158  099%  1
         * 017904548  001%  3
         */
        int[] a = Stream.generate(() -> random.nextInt(1000)).limit(10000000).mapToInt(i -> i).toArray();
        int[] b = Arrays.copyOf(a,a.length);//Stream.generate(() -> random.nextInt(1000)).limit(100).mapToInt(i -> i).toArray();

        StopWatch stopWatch = new StopWatch();
        /*stopWatch.start("1");
        smallSum(a);
        stopWatch.stop();*/
        // 假的归并,算法上时间复杂度和第一个相同.
       /* stopWatch.start("2");
        System.out.println("smallSum2");
        smallSum2(a);
        stopWatch.stop();*/

        //
        stopWatch.start("3");
        System.out.println("smallSum3");
        smallSum3(a);
        stopWatch.stop();


        stopWatch.start("4");
        System.out.println("smallSum4");
        smallSum4(b);
        stopWatch.stop();
        System.out.println(stopWatch.prettyPrint());

    }

    /***   smallSum4   *****/
    public static void smallSum4(int[] a) {
        System.out.println(smallSum4(a, 0, a.length - 1));
    }

    public static int smallSum4(int[] a, int start, int end) {
        if (start < 0 || start >= end) {
            return 0;
        }
        int mid = (start + end) / 2;
        int[] tempA = new int[a.length];
        return smallSum3(a, start, mid) + smallSum3(a, mid + 1, end) + merge3(a, start, end, mid, tempA);
    }

    /**
     * 一边归并一边排序
     */
    public static int merge3(int[] a, int start, int end, int mid, int[] tempA) {
        int sum = 0;
        //int[] tempA = new int[end - start + 1];
        int tempIndex = 0;
        int i = start, j = mid + 1;
        while (i <= mid && j <= end) {
            if (a[i] <= a[j]) {
                sum += a[i] * (end - j + 1);
                tempA[tempIndex++] = a[i++];
            } else {
                tempA[tempIndex++] = a[j++];
            }
        }
        while (i <= mid) {
            tempA[tempIndex++] = a[i++];
        }
        while (j <= end) {
            tempA[tempIndex++] = a[j++];
        }
        //复制tempA 给 原数据
        //System.out.println("start:" + start + "end:" + end + "mid:" + mid + "tempIndex:" + tempIndex);
        tempIndex--;
        while (tempIndex >= 0) {
            a[start + tempIndex] = tempA[tempIndex--];
        }
       /* for (int k = 0; k < tempIndex; k++) {
            a[start + k] = tempA[k];
        }*/
        //System.out.println(String.format("start:%d ,end: %d ,mid:%d ,sum:%d", start, end, mid, sum));
        return sum;
    }


    /***   smallSum2   *****/

    /***   smallSum3   *****/

    public static void smallSum3(int[] a) {
        System.out.println(smallSum3(a, 0, a.length - 1));
    }

    public static int smallSum3(int[] a, int start, int end) {
        if (start < 0 || start >= end) {
            return 0;
        }
        int mid = (start + end) / 2;
        return smallSum3(a, start, mid) + smallSum3(a, mid + 1, end) + merge2(a, start, end, mid);
    }

    /**
     * 一边归并一边排序
     */
    public static int merge2(int[] a, int start, int end, int mid) {
        int sum = 0;
        int[] tempA = new int[end - start + 1];
        int tempIndex = 0;
        int i = start, j = mid + 1;
        while (i <= mid && j <= end) {
            if (a[i] <= a[j]) {
                sum += a[i] * (end - j + 1);
                tempA[tempIndex++] = a[i++];
            } else {
                tempA[tempIndex++] = a[j++];
            }
        }
        while (i <= mid) {
            tempA[tempIndex++] = a[i++];
        }
        while (j <= end) {
            tempA[tempIndex++] = a[j++];
        }
        //复制tempA 给 原数据
        //System.out.println("start:" + start + "end:" + end + "mid:" + mid + "tempIndex:" + tempIndex);

        for (int k = 0; k < tempIndex; k++) {
            a[start + k] = tempA[k];
        }
        //System.out.println(String.format("start:%d ,end: %d ,mid:%d ,sum:%d", start, end, mid, sum));
        return sum;
    }

    /**
     * 归并处理
     */
    public static void smallSum2(int[] a) {
        System.out.println(smallSum2(a, 0, a.length - 1));
    }

    public static int smallSum2(int[] a, int start, int end) {
        if (start < 0 || start >= end) {
            return 0;
        }
        int mid = (start + end) / 2;
        return smallSum2(a, start, mid) + smallSum2(a, mid + 1, end) + merge(a, start, end, mid);
    }

    public static int merge(int[] a, int start, int end, int mid) {
        int sum = 0;
        for (int i = start; i <= mid; i++) {
            for (int j = mid + 1; j <= end; j++) {
                if (a[i] <= a[j]) {
                    sum += a[i];
                    System.out.println(++count3);
                }
            }
        }
        System.out.println(String.format("start:%d ,end: %d ,mid:%d ,sum:%d", start, end, mid, sum));
        return sum;
    }

    /***smallSum1*****/

    public static void smallSum(int[] a) {
        int sum = 0;
        for (int i = 0; i < a.length; i++) {
            sum += smallSum(a, i);
        }
        System.out.println(sum);
    }

    /**
     * 暴力破解 n的方
     */
    public static int smallSum(int[] a, int i) {
        int temp = a[i];
        int sum = 0;
        for (int j = 0; j < i; j++) {
            if (a[j] <= temp) {
                sum += a[j];
                //System.out.println(++count1);
            }
        }
        return sum;
    }
}

